/*
 * @Author: Tendo 
 * @Date: 2021-11-03 11:04:19 
 * @Last Modified by: Tendo
 * @Last Modified time: 2021-11-03 11:14:15
 */
/**
 * @param {number} n
 * @param {number} k
 * @return {number[][]}
 */
let res = [], // 存放符合条件结果的集合
    path = []; // 用来存放符合条件结果
var combine = function (n, k) {
    res = []
    backtracking(n, k, 1)
    return res
};
var backtracking = (n, k, startIndex) => {
    if (path.length === k) {
        res.push([...path])
        return
    }
    // 所以，可以剪枝的地方就在递归中每一层的for循环所选择的起始位置。
    // 如果for循环选择的起始位置之后的元素个数 已经不足 我们需要的元素个数了，那么就没有必要搜索了。
    // for (let i = startIndex; i <= n; i++) {
    for (let i = startIndex; i <= n - (k - path.length) + 1; i++) {// i为本次搜索的起始位置
        path.push(i) // 处理节点
        backtracking(n, k, i + 1); // 递归
        path.pop(); // 回溯，撤销处理的节点
    }
}